


/*Cormen, Leiserson, Rivest, Stein*/

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <cmath>


using namespace std;

void merge(int A[], int p, int q, int r);
//void mergeSort(int A[], int p, int r);

int main(void) {

    //An array that holds the numbers to be sorted
    int A[20] = {0, 1, 3, 4, 8, 9, 16, 29, 30, 32, 1, 3, 7, 13, 17, 19, 29, 31, 41, 57};
    int p = 0;
    int q = 9;
    int r = 19;

    //mergeSort(A, p, r);

    cout<<"A demonstration of Merge sort\n";
    cout<<"Input array (unsorted): A";
    for (int l = 0; l <= 19; l++) {
        cout << "["<<A[l]<<"]";
    }

    cout<<"\nAfter sorting..."<<endl;
    merge(A,p,q,r);

    return 0;
}

/*
void mergeSort(int A[], int p, int r) {

    int q;

    if (p < r) {
        q = floor((p + r) / 2);
        mergeSort(A, p, q);
        mergeSort(A, q + 1, r);
        merge(A, p, q, r);

    }

}
*/

void merge(int A[], int p, int q, int r) {

    int n1 = q - p + 1;
    int n2 = r - q;
    int i, j, k;

    int L[n1 + 1];
    int R[n2 + 1];

    for (i = 0; i < n1; i++) {
        L[i] = A[p + i];
    }

    for (j = 0; j < n2; j++) {
        R[j] = A[q + j + 1];
    }

    L[n1 + 1] = 50;
    R[n2 + 1] = 50;

    i = 0;
    j = 0;

    for (k = p; i < r; k++) {

        if (L[i] <= R[j]) {
            A[k] = L[i];
            i = i + 1;
        } else {
            A[k] = R[j];
            j = j + 1;
        }
    }

}

